Skip to main content

Topological Sort

  • Video source
  • Topological sort algorithm can find a topological ordering in O(V+E)
  • A graph with a cycle can not have a valid ordering
    • only works on as-cyclic directed graph(no cycle)
  • Topological sort is not unique, there can be multiple ordering.
  • Real world application
    • Course scheduling
    • Program dependencies think npm libraries
    • During program compilation

Topological Ordering of a Tree​

Ordering of a tree is basically a reverse BFS/level-search….starting from leaf nodes and going up.

Topological Sort Algorithm DFS Version​

  • Pick an un-visited node
  • Do DFS on starting with node…visit only un-visited nodes
  • On the recursive callback of the DFS. add the current node to the topological ordering in reverse order.
def topsort(graph):

	N = graph.numberOfNodes()
	V = [False]*N
	ordering = [0]*N
	i = N - 1

	for at in range(N):
		if V[at] == False:
			i = dfs(i, at, V, ordering, graph)

	return ordering

def dfs(i, at, V, ordering, graph):
	V[at] = True

	edges = graph.getEdgesOf(at)

	for edge in edges:
		if V[edge.to] == False:
			i = dfs(i, edge.to, V, ordering, graph)

	ordering[i] = at
	return i - 1

Topological Sort Algorithm BFS Version​